function Node(data,left,right){
    this.data = data;
    this.left = left;
    this.right = right
}

Node.prototype={
    show:function(){
        console.log(this.data);
    }
}

function Tree(){
    this.root = null;
}

Tree.prototype={

    //二叉树插入操作
    insert:function(data){
        var node = new Node(data,null,null);
        if(!this.root){
            this.root = node;
            return;
        }
        var current = this.root;
        var parent = null;
        while(current){
            parent = current;
            if(data<parent.data){
                current = current.left;
                if(!current){
                    parent.left = node;
                    return;
                }
            }else{
                current = current.right;
                if(!current){
                    parent.right = node;
                    return;
                }
            }
        }
    },

    //前序遍历
    preOrder:function(node){
        if(node){
            node.show();
            this.preOrder(node.left);
            this.preOrder(node.right)
        }
    },

    //中序遍历
    middleOrder:function(node){
        if(node){
            this.middleOrder(node.left);
            node.show();
            this.middleOrder(node.right);
        }
    },

    //后序遍历
    laterOrder:function(node){
        if(node){
            this.laterOrder(node.left);
            this.laterOrder(node.right);
            node.show();
        }
    },

    //查找最小值
    getMin:function(){
        var current = this.root;
        while(current){
            if(!current.left){
                return current.data;
            }
            current=current.left;
        }
    },

    //查找最大值
    getMax:function(){
        var current = this.root;
        while(current){
            if(!current.right){
                return current.data;
            }
            current=current.right;
        }
    },

    //获取二叉树的深度即层数
    getDeep:function(node,deep){
        deep = deep || 0;
        if(node == null){
            return deep;
        }
        deep++;
        var dleft = this.getDeep(node.left,deep);
        var dright = this.getDeep(node.right,deep);
        return Math.max(dleft,dright);
    },

    //树查找
    getNode:function(data,node){
        if(node){
            if(data === node.data){
                return node.data;
            }else if(data < node.data){
                return this.getNode(data,node.left);
            }else{
                return this.getNode(data,node.right);
            }
        }else{
            return null;
        }
    }
}
var t = new Tree();
t.insert(3);
t.insert(8);
t.insert(1);
t.insert(2);
t.insert(5);
t.insert(7);
t.insert(6);
t.insert(0);
//console.log(t);
// t.middleOrder(t.root);
// t.preOrder(t.root);
// console.log(t.getMin(), t.getMax());
// console.log(t.getDeep(t.root, 0));
console.log(t.getNode(5,t.root));

//二分查找
function binarySearch(data,arr,start,end){
    arr.sort();
    if(start > end){
        return -1;
    }
    var mid = Math.floor((end+start)/2);
    if(data == arr[mid]){
        return mid;
    }else if(data<arr[mid]){
        return binarySearch(data,arr,start,mid-1);
    }else{
        return binarySearch(data,arr,mid+1,end);
    }
}
var arr=[3,7,5,6,8,2,4]
console.log(binarySearch(4,arr,0,arr.length))

//二叉树中序遍历非递归实现
// 取跟节点为目标节点，开始遍历
// 1.左孩子入栈 -> 直至左孩子为空的节点
// 2.节点出栈 -> 访问该节点
// 3.以右孩子为目标节点，再依次执行1、2、3
var inorderTraversal = function(root){
    const result =[];
    const stack = [];
    let current = root;
    while(current || stack.length>0){
        while(current){
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        result.push(current.data);
        current = current.right;
    }
    return result;
}

//二叉树前序遍历非递归实现
// 取跟节点为目标节点，开始遍历
// 1.访问目标节点
// 2.左孩子入栈 -> 直至左孩子为空的节点
// 3.节点出栈，以右孩子为目标节点，再依次执行1、2、3
var preorderTraversal = function(root){
    const result = [];
    const stack = [];
    let current = root;
    while(current || stack.length>0){
        while(current){
            result.push(current.data);
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        current = current.right;
    }
    return result;
}

//二叉树后序遍历非递归实现
// 取跟节点为目标节点，开始遍历
// 1.左孩子入栈 -> 直至左孩子为空的节点
// 2.栈顶节点的右节点为空或右节点被访问过 -> 节点出栈并访问他，将节点标记为已访问
// 3.栈顶节点的右节点不为空且未被访问，以右孩子为目标节点，再依次执行1、2、3
var lastorderTraversal = function(root){
    const result = [];
    const stack = [];
    let last = null; //标记上一个访问节点
    let current = root;
    while(current || stack.legnth>0){
        while(current){
            stack.push(current);
            current = current.left;
        }
        current = stack[stack.length-1];
        if(!current.right || current.right == last){
            current = stack.pop();
            result.push(current.data);
            last = current;
            current = null; //继续出栈
        }else{
            current = current.right;
        }
    }
    return result;
}